package br.com.rookgraph.aproximativo;

import br.com.rookgraph.Edge;
import br.com.rookgraph.Graph;
import br.com.rookgraph.Swap;
import br.com.rookgraph.heuristica.Algoritm;
import br.com.rookgraph.utils.ArrayUtils;

public class Approximative implements Algoritm {

	public Graph getOriginal() {
		return original;
	}

	public void setOriginal(Graph original) {
		this.original = original;
	}

	public Graph getTree() {
		return tree;
	}

	public void setTree(Graph tree) {
		this.tree = tree;
	}

	private Graph original;
	private Graph tree;
	
	public Approximative(Graph original, Graph tree) {
		this.original = original;
		this.tree = tree;
	}
	
	@Override
	public Graph execute() {
		oneFlip();
		
		twoFlip();
		
		return tree;
	}


	private void oneFlip() {
		boolean improves;
		
		/** DO IMPROVING ONE-FLIPS WHILE THERE'S ANY */
		do {
			improves = false;
			Edge[] cuttingListOneFlip = createCuttingList(this.tree);
			
			for (Edge cutEdge : cuttingListOneFlip) {
				this.tree.removeEdge(cutEdge);
				
				Edge[] repList = createReplacementListToCuttingEdge(this.tree, cutEdge);
				
				this.tree.addEdge(cutEdge);
				
				for (Edge repEdge : repList) {
					improves = isImproving(this.tree, new Swap(cutEdge, repEdge, tree));
					
					if (improves) {
						tree.swapEdge(new Swap(cutEdge, repEdge));
						break;
					}
				}
				
				if (improves) {
					break;
				}
			}
		} while (improves);
	}


	private void twoFlip() {
		boolean improves;
		
		/** DO IMPROVING TWO-FLIPS WHILE THERE'S ANY */
		do {
			improves = false;
			
			// Cria lista de arestas para remover de tree
			Edge[] cuttingListTwoFlip = createCuttingList(this.tree);
			
			// Para cada aresta a remover, separa as duas árvores geradas com sua remoção (tree_1 e tree_2)
			// e, para cada uma delas, criar a segunda lista de remoção de arestas.
			for (Edge cutEdge : cuttingListTwoFlip) {
				this.tree.removeEdge(cutEdge);
				
				int[] seg_1 = this.tree.reached(cutEdge.origin, new int[this.tree.getOrder()]);
				int[] seg_2 = this.tree.reached(cutEdge.target, new int[this.tree.getOrder()]);
				
				Graph tree_1 = createNewTreeWithNodes(seg_1, this.tree);
				Graph tree_2 = createNewTreeWithNodes(seg_2, this.tree);
				
				this.tree.addEdge(cutEdge);
				
				improves = improvingTree_(improves, cutEdge, tree_1) || improvingTree_(improves, cutEdge, tree_2);
				
				if (improves) {
					break;
				}
			}
		} while (improves);
	}
	
	
	private boolean improvingTree_(boolean improves, Edge cutEdge, Graph sub_tree) {
		Edge[] cuttingList_sub = createCuttingList(sub_tree);
		
		for (Edge cutEdge_sub : cuttingList_sub) {
			sub_tree.removeEdge(cutEdge_sub);

			Edge[] repList_sub = createReplacementListToCuttingEdge(sub_tree, cutEdge_sub);
			
			sub_tree.addEdge(cutEdge_sub);
			
			for (Edge repEdge_sub : repList_sub) {
				// Fazer substituição sobre em Sub_tree
				tree.removeEdge(cutEdge_sub);
				tree.addEdge(repEdge_sub);
				
				tree.removeEdge(cutEdge);
				Edge[] repList = createReplacementListToCuttingEdge(tree, cutEdge);
				tree.addEdge(cutEdge);
				
				tree.removeEdge(repEdge_sub);
				tree.addEdge(cutEdge_sub);
				
				for (Edge repEdge : repList) {
					Swap swap1 = new Swap(cutEdge, repEdge, tree);
					Swap swap2 = new Swap(cutEdge_sub, repEdge_sub, tree);
					
					improves = isImproving(tree, swap1, swap2);
					
					if (improves) {
						tree.swapEdge(swap1);
						tree.swapEdge(swap2);
						
						break;
					}
				}
				
				if (improves) {
					break;
				}
			}
			
			if (improves) {
				break;
			}
		}
		return improves;
	}

	private Graph createNewTreeWithNodes(int[] nodes, Graph tree) {
		Graph newTree = new Graph(tree.order);
		int[][] edgesNewTree = newTree.edges();
		
		for (Integer node : nodes) {
			int[] adjacentes = tree.getAdjacentes(node);
			
			for (Integer adj : adjacentes) {
				edgesNewTree[node-1][adj-1] = 1;
			}
		}
		
		return newTree;
	}

	/**
	 * REVISAR!
	 * 
	 * @param swaps
	 * @param tree
	 * @return
	 */
	private boolean isImproving(Graph tree, Swap... swaps) {
		int pathNodesBefore = countPathNodes(tree);
		int cubicNodesBefore = countCubicNodes(tree);
		
		for (Swap sw : swaps) {
			tree.swapEdge(sw);
		}
		
		int pathNodesAfter = countPathNodes(tree);
		int cubicNodesAfter = countCubicNodes(tree);
		
		for (Swap sw : swaps) {
			tree.undoSwap(sw);
		}
		
		if (pathNodesAfter > pathNodesBefore || (pathNodesAfter == pathNodesBefore && cubicNodesAfter < cubicNodesBefore)) {
			return true;
		} else {
			return false;
		}
	}
	
	private int countCubicNodes(Graph tree) {
		int cubicNodes = 0;
		
		for (int i = 0; i < tree.order; i++) {
			cubicNodes += tree.grau(i+1) == 3 ? 1 : 0;
		}
		
		return cubicNodes;
	}

	private int countPathNodes(Graph tree) {
		int pathNodes = 0;
		
		for (int i = 0; i < tree.order; i++) {
			pathNodes += tree.grau(i+1) < 3 ? 1 : 0;
		}
		
		return pathNodes;
	}

	protected Edge[] createReplacementListToCuttingEdge(Graph tree, final Edge arestaCut) {
		int[] seg1 = tree.reached(arestaCut.origin, new int[tree.getOrder()]);
		int[] seg2 = tree.reached(arestaCut.target, new int[tree.getOrder()]);

		Edge[] arestasRep = new Edge[seg1.length * seg2.length];

		int count = 0;

		for (int vSeg1 : seg1) {
			for (int vSeg2 : seg2) {
				final Edge currentArest = new Edge(vSeg1, vSeg2);

				if (!currentArest.equals(arestaCut) && (this.original.grau(vSeg1) > 1 && this.original.grau(vSeg2) > 1)) {
					if (!tree.hasEdge(vSeg1, vSeg2) && this.original.hasEdge(vSeg1, vSeg2)) {
						if (!ArrayUtils.contains(currentArest, arestasRep)){
							arestasRep[count++] = currentArest;
						}
					}
				}
			}
		}

		Edge[] listRep = new Edge[count];
		System.arraycopy(arestasRep, 0, listRep, 0, count);

		return listRep;
	}
	
	private Edge[] createCuttingList(Graph tree) {
		int order = tree.getOrder();
		int count = 0;
		Edge[] edgesCut = new Edge[order * order];

		for (int branch : tree.getBranchs()) {
			for (int adjacente : tree.getAdjacentes(branch)) {
				Edge candidata = new Edge(branch, adjacente);
				
				if (!ArrayUtils.contains(candidata, edgesCut) && (this.original.grau(adjacente) > 1)) {
					edgesCut[count++] = candidata;
				}
			}
		}

		Edge[] listCut = new Edge[count];
		System.arraycopy(edgesCut, 0, listCut, 0, count);
		
		return listCut;
	}

}
